The present application relates to nodal position estimation in wireless networks, and more particularly to position based services in wireless sensor networks.
A Wireless Sensor Network (WSN) is a group of sensor nodes performing some sensing tasks jointly through wireless radio interface. Unlike other wireless networks, WSNs are characterized by many nodes (usually in excess of a hundred) of high density, low computational power and limited transmission range. Depending on the application, sensor nodes can be stationary or mobile. A stationary (or low mobility) network discussed here is commonly used for environmental monitoring type of applications, which is one of the major applications of WSNs. These applications include e.g. monitoring the temperature or moisture variation over an area of interest, detecting intruders within private premises, or exploring unknown surrounding environment without risking human lives.
For most applications of WSNs, it is very useful to know the nodal positions where the data is measured. Nodal position is particularly useful in, the following two cases: position-based routing and position specific applications.
Position-Based Routing
As the transmission range of each node in a WSN is limited, data forwarding would normally be required to go through multi-hops. It is therefore desirable to lower the number of intermediate nodes, as this implies less communication is required, and thus reducing energy consumption. Optimization of the network topology (in terms of positions of neighboring nodes) provides useful constraints for route correctness and efficiency, and thereby leads to a reduction in the packet loss to the destination nodes, the power consumed for routing, and/or the number of hops to the destination (and hence increase in the throughput).
Position-Specific Applications
Position information of the nodes is essential for their proper functioning in position-specific applications. Examples are locating a problematic area (due to flooding, chemical, etc) in a city or forest, or tracking the parking position of one's car. Very often sensors are used to monitor an area of interest, and in such cases it is essential to have the position of the node bound to its measurement.
Many techniques have been proposed to estimate nodal positions, focusing on different types of wireless environment with different requirements. Hence, not all schemes are applicable in a wireless sensor network setting. One example is the GPS system in which nodal positions are estimated via communications between GPS devices and satellites traveling in space. While it provides a fairly accurate estimation up to meters, it requires costly special receivers and high energy demanding for networks with a large number of nodes, such as sensor networks.
However, position information from GPS is useful as it provides an existing coordinate system for use. It is therefore a common practice to assume only a small amount of nodes in a sensor network with GPS capability as reference nodes or landmarks, while the nodal positions of other nodes are estimated by using the reference nodes' positions together with other information such as distances and angles. In general, depending on the way positions are estimated, position estimation techniques for sensor networks may be divided into the following three categories: distance-based, angle-based and pattern-based.
Distance-Based
This category of techniques makes use of distances between nodes and mathematical tools such as trilateration and multi-dimensional scaling (MDS) for position estimation. The distances could be represented discretely and the loss of accuracy can be compensated by aggregating measurements from a number of nodes. In particular, if the distances are represented in a binary manner, they are often referred to as “connectivities” instead. While these techniques usually have the advantages of simple calculation and without special hardware requirements, they are often prone to measurement errors incurred in measuring distances. Depending on the way distances are measured, the degree of error varies with the changing environment.
Angle-Based
Techniques in this category make use of measured angles among nodes to estimate nodal positions via triangulation. Because a triangulation problem can be transformed into a trilateration problem, angle-based techniques enjoy the simplicity in calculation similar to that in distance-based techniques. Further, they are less prone to measurement error caused by signal attenuation, and have better energy conservation and bandwidth utilization as the signal can be sent with a direction. However, this category requires special hardware to measure the angles (e.g. Cricket compasses), which may lead to an increase in cost and energy requirements.
Pattern-Based
In this category, certain patterns (e.g. signal strength patterns) are observed and are related to positions, which are then used either directly for position estimation or as input for distribution functions for more sophisticated results. While these techniques are less prone to measurement errors in ranges compared with the previous two categories, in most cases, however, a prior knowledge of the map and a careful design of to-be-sensed patterns are necessary, which may not be available or practical in certain wireless sensor networks.
Distributed Position Estimation for Wireless Networks
The present application describes a new distance-based architecture. Each node in this scheme can control its transmission power to discrete values. By varying its transmission power a node can discover its neighbors at discrete distances. Use of a coarse (quantized) distance measurement makes the scheme less environmentally sensitive than architectures which use more precise distance measurements as input. Each node then gathers distance information from immediate neighbors by voluntarily exchanging collected distance information with each other. The accuracy is compensated by each node aggregating distance information from its neighbors. A node then estimates its own position with respect to other nodes by applying Multidimensional Scaling (MDS) on the collected distance information.
Position estimates are refined in a progression which starts from some bootstrap nodes, and propagates gradually outwards to nodes further away. (At least some bootstrap nodes are preferably “landmark” nodes, which are preferably equipped with its own accurate position information. One example of less preferable method of getting its own accurate position information is via GPS). Note that accuracy in the context of position information is referring the fact that while a node aggregates distance information it will have distance information between more and more nodes by running, for instance, a shortest paths algorithm against the collected data. A bootstrap node then broadcasts its position along with relative positions of its immediate neighbors. The neighbors' positions are relative because they subject to rotation and reflection (but not translation). Each non-bootstrap node further collects reference positions of immediate neighbors reachable via a single hop by voluntarily exchanging position information with each other or by receiving bootstrap nodes' position broadcasting. When insufficient position information is collected, each node then employs a special polling approach to request its immediate neighbors for position information. Finally a non-bootstrap node employs MDS or some minimization algorithm to minimize the errors in estimation.
The actual complete position estimation employs refining steps. First, each general node re-orients its corresponding position relative to each of the bootstrap nodes, after receiving position updates from others and using them as reference points. Since after this step it will only have a couple of positions, each consistent with the corresponding bootstrap node, so the second refining step is to use such relative positions together with the positions of the bootstrap nodes to get the absolute position with a minimization equation, one example is defined in later section.
Contrary to angle-based and pattern-based techniques, this scheme does not require any special hardware, nor powerful base stations with overlapping coverage, nor pre-knowledge of the area of interest, nor recursive probabilistic processes. These differences, together with the fact that it is a distributed scheme and therefore spreads the computational stress over numerous nodes, make it very suitable for position estimation in a WSN setting.
While the scheme can also be used in other wireless networks, it is particularly suitable for wireless sensor networks. Advantages of various disclosed embodiments include one or more of the following:                It is robust against measurement noise and channel fading/interference since only imprecise (quantized) information on the distances is needed.        It is fast and not computationally intensive, since a node only needs information from its neighbors and only information about its neighbors is calculated.        It is bandwidth efficient as information is exchanged within nodes in proximity only and bandwidth-inefficient global flooding is avoided.        It is cost effective since only a few devices with GPS capability are required to have positions estimated consistent with the GPS coordinate space.        It is robust to handle joining/leaving nodes.        It is capable to handle lower power nodes which take a minimal part in the estimation process. And        Finally, useful information for position-based routing is already embedded during the position estimation process, resulting in no or minimal extra transmission for efficient route determination.        